package com.scheuk.puzzles;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;
import java.lang.reflect.Array;

public class Permute implements Iterator {

   private final int size;
    //private final Object [] elements;  // copy of original 0 .. size-1
    private final int[] elements;  // copy of original 0 .. size-1
    private final Object ar;           // array for output,  0 .. size-1
    private final int [] permutation;  // perm of nums 1..size, perm[0]=0
 
    private boolean next = true;
 
    // will only work with int[]
    public Permute (int [] e) {
       size = e.length;
       elements = new int[size];    // not suitable for primitives
       System.arraycopy (e, 0, elements, 0, size);
       ar = Array.newInstance (e.getClass().getComponentType(), size);
       System.arraycopy (e, 0, ar, 0, size);
       permutation = new int [size+1];
       for (int i=0; i<size+1; i++) {
          permutation [i]=i;
       }
    }
       
    private void formNextPermutation () {
       for (int i=0; i<size; i++) {
          // i+1 because perm[0] always = 0
          // perm[]-1 because the numbers 1..size are being permuted
          Array.set (ar, i, elements[permutation[i+1]-1]);
       }
    }
 
    public boolean hasNext() {
       return next;
    }
 
    public void remove() throws UnsupportedOperationException {
       throw new UnsupportedOperationException();
    }

   private void swap (final int i, final int j) {
       final int x = permutation[i];
       permutation[i] = permutation [j];
       permutation[j] = x;
    }
 
    // does not throw NoSuchElement; it wraps around!
    public Object next() throws NoSuchElementException {
 
       formNextPermutation ();  // copy original elements
 
       int i = size-1;
       while (permutation[i]>permutation[i+1]) i--;
 
       if (i==0) {
          next = false;
          for (int j=0; j<size+1; j++) {
             permutation [j]=j;
          }
          return ar;
       }
 
       int j = size;
       
       while (permutation[i]>permutation[j]) j--;
       swap (i,j);
       int r = size;
       int s = i+1;
       while (r>s) { swap(r,s); r--; s++; }
 
       return ar;
    }
 
    public String toString () {
       final int n = Array.getLength(ar);
       final StringBuffer sb = new StringBuffer ("[");
       for (int j=0; j<n; j++) {
          sb.append (Array.get(ar,j).toString());
          if (j<n-1) sb.append (",");
       }
       sb.append("]");
       return new String (sb);
    }
 
    public static void main (String [] args) {
		int[] intNums = {9, 9, 6};
		Set<String> listA = new HashSet<String>();
		Set<int[]> listB = new HashSet<int[]>();
		for (Iterator<int[]> i = new Permute(intNums); i.hasNext(); ) {
          int [] a = (int []) i.next();
          listA.add(Arrays.toString(a));
          listB.add(a);
          System.out.println (i);
		}
		System.out.println("check listA : " + listA.toString());
		System.out.println("check listB : ");
		for (Iterator i = listB.iterator(); i.hasNext(); ) {
	          final int [] a = (int []) i.next();
	          System.out.println (Arrays.toString(a));
			}
    }
}